//
//  main.c
//  DataStructureProject
//
//  Created by zhangbaochuan on 2019/12/20.
//  Copyright © 2019 Geex. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "heapManager.hpp"

#include "SortHelper.h"


void swapArray(int *arr, int l, int r) {
    int temp = arr[l];
    arr[l] = arr[r];
    arr[r] = temp;
}

#pragma mark --二分查找

int binarySearch_ceil(int *arr, int n, int k) {
    int l = 0;
    int r = n;
    while (l < r) {
        
        int mid = l + (r - l)/2;
        if (k >= arr[mid]) {
            l = mid + 1;
        }
        if (k < arr[mid]) {
            r = mid;
        }
    }
    if (r - 1 >= 0 && arr[r - 1] == k) {
        return r - 1;
    }
    return r;
}

int binarySearch_floor(int *arr, int n, int k) {
    int l = -1;
    int r = n - 1;
    while (l < r) {
        // 使用向上取整避免死循环
        int mid = l + (r - l + 1)/2;
        if (k >= arr[mid]) {
            l = mid;
        }
        if (k < arr[mid]) {
            r = mid - 1;
        }
    }
    if (l + 1 < n -1 && arr[l + 1] == k) {
        return l + 1;
    }
    return l;
}

int binarySearch(int *arr, int n, int i) {
    int l = 0;
    int r = n - 1;
    int mid;
    while (l <= r) {
        mid = l + (r - l)/2;
        if (i == arr[mid]) {
            
            return mid;
        }
        if (i > arr[mid]) {
            l = mid + 1;
        }
        if (i < arr[mid]) {
            r = mid - 1;
        }
    }
    return -1;
}

void binarySearch_start(int *arr, int n)
{
    int i = rand() % n;
    int mid = binarySearch(arr, n, arr[i]);
    if (mid != -1) {
         printf("找到了i= %d  == %d",i,mid);
    }else {
        printf("没有找到");
    }
}


#pragma mark --堆、heapify 、shiftUP

void shiftUP(int *arr, int i) {
    
    while (i > 1 && arr[i] > arr[i/2]) {
        swapArray(arr, i, i/2);
        i = i/2;
    }
    
}

void shiftDown(int *arr, int i, int n) {
    while (2 * i < n) {
        int j = 2 *i;
        if (j + 1 < n && arr[j] < arr[j + 1]) {
            j = j + 1;
        }
        if (arr[j] > arr[i]) {
            swapArray(arr, i, j);
            i = j;
        }else {
            break;
        }
        
    }
}

void heapify(int *arr, int n, int i) {
    if (i >= n) {
        return;
    }
    int c1 = 2 * i + 1;
    int c2 = 2 * i + 2;
    int maxPartent = i;
    if (c1 < n && arr[c1] > arr[maxPartent]) {
        maxPartent = c1;
    }
    if (c2 < n && arr[c2] > arr[maxPartent]) {
        maxPartent = c2;
    }
    
    if (maxPartent != i) {
        int temp = arr[i];
        arr[i] = arr[maxPartent];
        arr[maxPartent] = temp;
        
        heapify(arr, n, maxPartent);
    }

}

void heapify_sort_build(int *arr, int num) {
    int last = num - 1;
    int parent = (last - 1)/2;
    for (int i = parent; i >= 0; i--) {
        heapify(arr, num, i);
    }
}

void heapify_sort_paixu (int *arr, int num) {
    heapify_sort_build(arr, num);
    for (int i = num - 1; i>= 0; i--) {
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        heapify_sort_build(arr, i);
        
    }
}

void heapify_sort_start(int *arr, int length) {
//    heapify_sort_build(arr, length);
    heapify_sort_paixu(arr, length);
}


#pragma mark --归并排序

/**
* 合并两个有序数列
* array[left]~array[mid]为第一组
* array[mid+1]~array[right]为第二组
* temp[]为存放两组比较结果的临时数组
*/
void merge(int arr[], int left, int mid, int right) {
    int temp[right - left + 1];
    int i = left;
    int j = mid + 1;
    int t = 0;
    // 比较左右两部分的元素，哪个小，把那个元素填入temp中
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[t++] = arr[i++];
        }else {
            temp[t++] = arr[j++];
        }
    }
    
    // 上面的循环退出后，把剩余的元素依次填入到temp中
    // 以下两个while只有一个会执行
    while (i <= mid) {
        temp[t++] = arr[i++];
    }
    
    while (j <= right) {
        temp[t++] = arr[j++];
    }
    
    t = 0;
    
    while (left <= right) {
        arr[left++] = temp[t++];
    }
}

void merge_sort_gui(int arr[], int left, int right) {
   
    if (left >= right) {
        return;
    }
    int mid = left + (right - left)/2;
    
    printf("1--letf=%d mid = %d  right = %d\n", left, mid, right);
    merge_sort_gui(arr, left, mid); // 递归归并左边元素
    printf("2--letf=%d mid = %d  right = %d\n", left, mid, right);
    merge_sort_gui(arr, mid + 1, right); // 递归归并右边元素
    printf("3--letf=%d mid = %d  right = %d\n", left, mid, right);

    //合并时  left  mid  right 怎么变化、
    merge(arr, left, mid, right);  //再将两个有序数列合并
}

void merge_sort(int arr[], int length) {
    
    merge_sort_gui(arr, 0, length -1);
//    printf("temp排序后\n");
    
}

//7  3 5 6  3  [i - 1 length)   待 i = 1
//3  5  7
              
#pragma mark --希尔排序 赋值
//gap = gap/2
//  0   1   2   3   4  5   6    7   8  9   数据下标
// 49  33  65  97  76  13  27  49  55  04  排序数据
// 步长 == 数组长度/2 == 5  然后插入排序算法
//首先按照步长去分组
// 49                  13
//     33                  27
//         65                  49
//             97                   55
//                 76                   04

//然后对每组进行排序
// 13                  49
//     27                  33
//         49                   65
//              55                  97
//                  04                  76

//当前数组变为
// 13  27  49   55  04 49  33   65  97  76

// 步长 == 上次步长/2 == 2
//按照步长去分组
// 13      49       04     33       97
//     27       55     49       65      76
//然后对每组进行插入排序
// 04      13       33     49       97
//     27       49     55       65      76
// 当前数组变为
// 04  27  13   49  33 55  49   65  97  76
//步长 == 上次步长/2 == 1
//然后对数组进行插入排序
// 04  13  27   33  49 49  55   65  76  97
//
void shellInsertion_sort(int array[], int last) {
    int times = 0;
    //分组  直到为1时 分组结束
    for (int gap = last/2; gap >= 1; gap = gap/2) {
        //对分组的数据进行插入排序
        for (int i = gap; i < last; i++) {
            int temp = array[i];
            int j = i - gap;
            for (; j >= 0 && array[j] > temp; j = j - gap) {
                array[j + gap] = array[j];
                times ++;
            }
            array[j+ gap] = temp;
        }
    }
    
    printf("\n排序后：");
    for (int i = 0; i< last; i++) {
        printf("%d ", array[i]);
    }
    printf("希尔排序赋值执行了：%d", times);
}

#pragma mark --希尔排序 交换
void shellExchangeInsertion_sort(int array[], int last) {
    int times = 0;
    int addGap = 5;
    //分组  直到为1时 分组结束
    for (int gap = last/addGap; gap >= 1; gap = gap/addGap) {
        if (gap < addGap){
            gap = 1;
        }
        //对分组的数据进行插入排序
        for (int i = gap; i < last; i++) {

            for (int j = i - gap; j >= 0 && array[j] > array[j + gap]; j = j - gap) {
                int temp = array[j];
                array[j] = array[j + gap];
                array[j+ gap] = temp;
                times ++;
            }
        }
        
    }
}


#pragma mark --直接插入排序
//直接插入排序
void insertion_sort(int array[], int last) {
    int i, j;
    int temp;
//    3  4    5    6  2
//    3  4    5    6  6
//    3  4    5    5  6
//    3  4    4    5  6
//    3  3    4    5  6
    
//
    for (i = 1; i < last; i++) {
        temp = array[i];
        j = i - 1;
        //与已经排序的数逐一比较，大于temp时，该数移后
        while ((j >= 0) && (array[j] > temp)) {
            array[j + 1] = array[j];
            j--;
        }
        //存在大于temp的数
//        if(j + 1 != i) {
            array[j + 1] = temp;
//        }
    }
}


#pragma mark --直接插入排序
//直接插入排序
        
void insert_sort(int *array, int n) {
    int i, j;
    int temp;
    for (i = 1; i < n; i++) {
        temp = *(array + i);
        for (j = i; j > 0 && *(array +j - 1) > temp; j--) {
            *(array + j) = *(array + j - 1);
        }
        *(array + j) = temp;
    }
    
}

#pragma mark --冒泡排序

void bubble_sort(int *array, int length){
    int temp;
    for (int i = 0; i< length; i++) {
        int flag = 0;
        for (int j = 0; j < length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag = 1;
            }
        }
        if (flag == 0) {
            break;
        }
    }
}
#pragma mark -- 三路快排

//r 为右侧 开区间  num = length
void threeQuick_sort (int *arr, int l, int r) {
    if (l >= r) {
        return;
    }
    
    int jt = r;
    int lt = l;
    int i = l + 1;
    int povnt = arr[l];
    while (i < jt) {
        if (arr[i] > povnt) {
            swapArray(arr, i, jt - 1);
            jt--;
        } else if (arr[i] < povnt) {
            swapArray(arr, i, lt + 1);
            lt++;
            i++;
        }else {
            i++;
        }
    }
    swapArray(arr, l, lt);
    threeQuick_sort(arr, l, lt);
    threeQuick_sort(arr, jt, r);
}

void three_Quick_start(int *arr, int r) {
    threeQuick_sort(arr, 0, r);
}

#pragma mark --双向冒泡
void doubleBubble_sort(int *array, int lenght) {
    int temp;
    for (int i = 0; i < lenght/2; i++) {
        int flag = 0;
        for (int j = 0; j < lenght - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag = 1;
            }
        }
        if (flag == 0) {
            break;
        }
        
        for (int j = lenght - i - 1; j > i; j--) {
            if (array[j] < array[j - 1]) {
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                flag = 1;
            }
        }
        if (flag == 0) {
            break;
        }
    }
}

#pragma mark -- 单路快排

int quick_simple_pivot(int arr[], int l, int r) {
    
        int p = arr[l];
        int i = l + 1;
        int k ;
        int temp;
        for (k = l + 1; k <= r && i<=r; k++) {
            if (arr[k] > p) {
                
            }
            if (arr[k] < p) {
                temp = arr[k];
                arr[k] = arr[i];
                arr[i] = temp;
                i ++;
            }
        }
        arr[l] = arr[i - 1];
        arr[i - 1] = p;
   
        return i - 1;
    
}

void quick_simple_sortPai(int arr[], int l, int r) {
    if (l < r) {
        int p = quick_simple_pivot(arr, l, r);
        quick_simple_sortPai(arr, l, p - 1);
        quick_simple_sortPai(arr, p + 1, r);
        
    }
}
void quick_simple_sort(int arr[], int r) {
    quick_simple_sortPai(arr, 0, r - 1);
}



#pragma mark --快速排序- 双路 赋值

/*
 第1步取基准  初始化  确定取值空间
 取基准V v = arr[l] int i = l   j = r
 <V  [l i)
 >V  (j  r]
+--------------------------------------------------------------+
| V |                                                          |
+--------------------------------------------------------------+
  l                                                          r
  i                                                          j

 第2步  遍历找到 arr[j] < v  arr[i] = arr[j]
+--------------------------------------------------------------+
| V |                                                       e |
+--------------------------------------------------------------+
  i                                                         j
                                                            
  第2.1步 arr[i]  = e   然后从i找 >V
+--------------------------------------------------------------+
| e |                                                      e  |
+--------------------------------------------------------------+
  i                                                        j
                                                           
 
第2.2步  找到k > V  arr[j] = arr[i]
+--------------------------------------------------------------+
| e |   k                                                   e |
+--------------------------------------------------------------+
        i                                                   j
                                                           
第2.3步  找到k > V  arr[j] = arr[i]
+--------------------------------------------------------------+
| e |   k                                                   k  |
+--------------------------------------------------------------+
  l     i                                                   j
 

 
第2.2步  i == j  arr[j] == arr[i]
 <V  [l i)
 >V  (j  r]
+--------------------------------------------------------------+
|     <V                 |  >V                                 |
+--------------------------------------------------------------+
l             <V         i
                         j

 第3步  i == j    arr[i] = 基准
+--------------------------------------------------------------+
|        <V             |V|            >V                      |
+--------------------------------------------------------------+
l                        i
                         j
*/

//        i = i++
//  7   6   9   4   5   8   j = r--
//  取出7作为基准  从右从左找出比7小的数放到 7的位置
//  5   6   9   4   5   8
//  从左往右取大于 比7大的数 放到之前5取到的位置
//  5   6   9   4   9   8
//  在从右往左取 没有比7 大的，
//  5   6   4   4   9   8
//  5   6   4   7   9   8
       
//l     j
//v  l   r

void pwrintArr(int a[],int l, int r) {
    for (int i = l; i <= r; i++) {
        printf("%d  ",a[i]);
    }
    printf("\n ");
}

void quick_sort(int a[], int l, int r)
{
    
    if (l < r)
    {
        int i,j,x;
        
        i = l;
        j = r;
        x = a[l];
        while (i < j)
        {
            while(j > i && a[j] > x)
                j--; // 从右向左找第一个小于x的数
            if(i < j){
                a[i] = a[j];

            }
            while(i < j && a[i] < x)
                i++; // 从左向右找第一个大于x的数
            if(i < j){
                a[j] = a[i];

            }
            
        }
        
        a[i] = x;
        quick_sort(a, l, i-1); /* i 左边 */
        quick_sort(a, i+1, r); /* 递归调用 */
    }
}

void quick_sortyuan(int *array, int length) {
    quick_sort(array, 0, length - 1);
}

#pragma mark --2路快排-交换

int quick_change(int *arr, int l, int r) {
    int p = arr[l];
    int i = l + 1;
    int j = r;
    int temp;
    while (l < r) {
        while (i <= j && arr[i] < p) {
            i++;
        }
        while (j >= i && arr[j] > p) {
            j--;
        }
        if (i > j) {
            break;
        }else {
//            交换
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    temp = arr[i - 1];
    arr[i- 1] = p;
    arr[l] = temp;
    return i -1;
}
void quick_sort_change(int *arr, int l, int r) {
    if (l < r) {
        int point = quick_change(arr, l, r);
        quick_sort_change(arr, l, point - 1);
        quick_sort_change(arr, point + 1, r);
        
    }
}
void quick_sort_changeStart(int *arr, int length) {
    quick_sort_change(arr, 0, length - 1);
}

//7 3 4 6  5  【0 length）
//         *
//3 7 4 6  5  【1 length）
//        *
//3 4 7  6 5

#pragma mark --选择排序
// 优化  交换次数
void select_sort(int *array, int length) {
    int temp;
    for (int i = 0; i< length - 1; i++) {
        for (int j = i + 1; j <length; j++) {
            if (array[i] > array[j]) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                
            }
        }
    }
}

//选择排序赋值
void select_sort_assignment(int *array, int length) {
    for (int i = 0; i< length; i++) {
        int temp = array[i];
        int flag = i;
        for (int j = i+ 1; j < length; j++) {
            if (array[i] > array[j]) {
                array[i] = array[j];
                flag = j;
            }
        }
        array[flag] = temp;
        
    }
}

int main(int argc, const char * argv[]) {
//   / insert code here...
    printf("Hello, 开始排序!\n");

//    1、随机数
//    2、没有重复的随机数
//    3、倒序的数据
//    4、有序的数据
//    5、近乎有序的数据
//    比较交换或赋值次数  比较耗时时间
    

    int num = 10;
    // 1、产生 n 个[rangL,rangR]之间的随机数
//    int *randomArray = generateRandomArray(num, 0, num);
    
    //2、不重复的[rangL,rangR]之间的随机数
//    int *array = generateNoRepeatRandomArray(num, 10, num + 10);
    
    //3、产生倒叙的数组
//    int *array = generateReverseArray(num);
    
    //4、有序的数据
    int *array = generateSequenceArray(num);
    
    //5、近乎有序的数据
//    int *array = generateRandomSequenceArray(num, num);
    
//    int *array = noRepeatRandomArray;
//    shellExchangeInsertion_sort(array, num);
//    testSort("希尔排序", shellExchangeInsertion_sort,array, num);
//    int array[10] = {1, 3, 5,7,8,9,10,12,14,15};
    printf("排序前\n");
    for(int i = 0; i < num; i++) {
        printf("%d  ", array[i]);
    }
//    printf("\n");
//    bubble_sort(array, num);
//    testSort("冒泡排序", bubble_sort, array, num);

//    merge_sort(array, num);
//    testSort("归并排序", merge_sort, array, num);
//    select_sort_assignment(array, num);
//    testSort("选择排序", select_sort_assignment, array, num);
    
    
//    insert_sort_assgnment(array, num);
//    testSort("插入排序", insert_sort_assgnment, array, num);
    
//    quick_sort(array, 0, num);
    int *arr = array;
//    testSort("双路快速排序- 赋值", quick_sortyuan, arr, num);
//    testSort("单路快速排序", quick_simple_sort, array, num);
//    testSort("双路快速排序- 交换", quick_sort_changeStart, arr, num);
//    testSort("堆heapify", heapify_sort_start, array, num);
//    testSort("三路快排", three_Quick_start, array, num);
    
//    testSort("二分查找", binarySearch_start, array, num);
    //shiftup
//    int *arr1 = {0};
//    for (int i = 1; i< 10; i++) {
//        shiftUP(arr, i);
//    }
//    swapArray(arr, 1, 9);
//    shiftDown(arr, 1, num - 1);
//    int search = binarySearch_ceil(arr, num, 6);
//    printf("search = %d", arr[search]);
//    printf("排序后\n");
//    for(int i = 0; i < num; i++) {
//        printf("%d  ", arr[i]);
//    }
    return 0;
}

